import java.util.*;


public class Solution4 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        // write code here
        int n = s1.length();
        int m = s2.length();
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        //dp表会列出数字，第一次相等时dp[i][j]=1,如果dp[i][j]=1，
        //              则dp[i+1][j]/dp[i][j+1]都至少和dp[i][j]一样;
        //第二次相等时dp[i][j] = 2
        int[][] dp = dfs(ch1,ch2);
        n = s1.length()-1;
        m = s2.length()-1;
        StringBuilder res = new StringBuilder();
        while(n >= 0 && m >= 0) {
            if(n > 0 && dp[n][m] == dp[n-1][m]) {
                n--;
            } else if(m > 0 && dp[n][m] == dp[n][m-1]) {
                m--;
            } else{
                if(dp[n][m] != 0) {
                    res.append(ch1[n]);
                }
                n--;
                m--;
            }
        }
        String r = res.reverse().toString();
        if(r.equals("")) {
            return new String("-1");
        }
        return r;

    }
    public int[][] dfs(char[] c1,char[] c2) {
        int[][] dp = new int[c1.length][c2.length];
        for(int i = 0;i<c1.length;i++) {
            for(int j = 0;j<c2.length;j++) {
                if(i == 0 && j == 0) {
                    dp[i][j] = c1[0] == c2[0]?1:0;
                } else if(i == 0){
                    if(c1[i] == c2[j]) {
                        dp[i][j] = 1;
                    }
                    dp[i][j] = Math.max(dp[i][j-1],dp[i][j]);
                } else if(j == 0) {
                    if(c1[i] == c2[j]) {
                        dp[i][j] = 1;
                    }
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j]);
                } else {
                    if(c1[i] == c2[j]) {
                        dp[i][j] = 1;
                    }
                    int max = Math.max(dp[i-1][j],dp[i][j-1]);
                    dp[i][j] = Math.max(dp[i-1][j-1] + dp[i][j],max);
                }
            }
        }
        return dp;
    }
}